/*
 * @Description: 
 * @version: 
 * @Author: Eve
 * @Date: 2019-06-20 16:40:34
 * @LastEditors: Eve
 * @LastEditTime: 2020-04-22 10:41:26
 */
var arr1 = [1, 2, 3, 4, 6, 3, 2.9, 0.1, -2]
// for (let i = 0; i < Math.random() * 999999; i++) {
// 	arr1.push(i * Math.random())
// }
function maxArrNum(arr) {
	return Math.max.apply(null, arr)
}

// console.log(maxArrNum(arr1))

// 冒泡排序
/* 
1、比较两个相邻的元素，如果后一个比前一个大，则交换位置。
2、 第一轮的时候最后一个元素应该是最大的一个。
3、按照第一步的方法进行两个相邻的元素的比较，由于最后一个元素已经是最大的了，所以最后一个元素不用比较。
*/
function popSort(arr) {
	console.time('pop')
	let copyArr = Array.from(arr),
		len = copyArr.length
	for (let i = 0; i < len; i++) {
		for (let j = 0; j < len - i - 1; j++) {
			if (copyArr[j] > copyArr[j + 1]) {
				;[copyArr[j], copyArr[j + 1]] = [copyArr[j + 1], copyArr[j]]
			}
		}
	}
	console.timeEnd('pop')
	return copyArr
}
popSort(arr1)
// 快排
/* 

1、在数据集之中，找一个基准点，将数据分成两个部分，一部分比另外一部分所有的数据都要小，
2、建立两个数组，分别存储左边和右边的数组
3、利用递归进行下次比较
*/

function quickSort(arr) {
	console.time('quick')
	let copyArr = Array.from(arr)
	function sort(_arr) {
		if (_arr.length <= 1) return _arr
		let base = _arr.splice(Math.floor(_arr.length / 2), 1)[0],
			left = [],
			right = []
		for (let i = 0; i < _arr.length; i++) {
			if (_arr[i] < base) {
				left.push(_arr[i])
			} else {
				right.push(_arr[i])
			}
		}
		return sort(left).concat([base], sort(right))
	}
	console.timeEnd('quick')
	return sort(copyArr)
}

function quickSort2(arr) {
	console.time('q2')
	let tmpArr = Array.from(arr)
	function sort(_arr) {
		if (_arr.length <= 1) return _arr
		let left = [],
			right = [],
			base = _arr.splice(Math.floor(_arr.length / 2), 1)[0]
		for (let i = 0, val; (val = _arr[i++]); ) {
			;(val < base ? left : right).push(val)
		}
		// for (let i = 0; i < _arr.length; i++) {
		// 	if (_arr[i] < base) {
		// 		left.push(_arr[i])
		// 	} else {
		// 		right.push(_arr[i])
		// 	}
		// }
		return [...sort(left), base, ...sort(right)]
		// return sort(left).concat([base], sort(right))
	}
	console.timeEnd('q2')
	return sort(tmpArr)
}
quickSort2(arr1)
quickSort(arr1)

// 正则插件测试
// let reg = newFunction()
// function newFunction() {
// 	return /^[\w]+@[\w|\d]+\..+/gim
// }
